package top.ivansong92.example.leetcode.learning.data.struct.array.sort;

/**
 * 快排
 */
public class QuickSort implements ArraySort {
    @Override
    public void sort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        doSort(array, 0, array.length -1);
    }

    private void doSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start, right = end;
        int val = array[left];
        while (left < right) {
            while (left < right && array[right] >= val) {
                right --;
            }
            array[left] = array[right];
            while (left < right && array[left] <= val) {
                left ++;
            }
            array[right] = array[left];
        }
        array[left] = val;
        doSort(array, start, left - 1);
        doSort(array, left + 1, end);
    }
}
